#pragma once
#include "base/noncopyable.h"
#include "base/function.hpp"
#include "base/config.h"

#include <deque>
#include <tuple>

#include <memory.h>
namespace net_tools::base::detail{

template<typename DATAPTR,typename DATAKEY>
class Bplustreeleaf{
 public:
  Bplustreeleaf(){
    memset(this,0,sizeof(Bplustreeleaf));
    level_ = 0;
  };
  ~Bplustreeleaf(){
    for(int count = 0;count < size_;++count){
        delete reinterpret_cast<DATAPTR>(ptr_[count]);
    }
  };
  int            level_;
  int            size_; //now timevent size
  DATAKEY        key_[_C::DEFAULT_BPLUSTREE_SIZE+1];
  DATAPTR        ptr_[_C::DEFAULT_BPLUSTREE_SIZE+1];
  Bplustreeleaf* next_;
  Bplustreeleaf* before_;
};

template<typename DATAPTR,typename DATAKEY>
class Bplustreenode{
 public:
  Bplustreenode(int level){
    memset(this,0,sizeof(Bplustreenode));
    level_ = level;
  };
  ~Bplustreenode(){
    if (level_ == 1)
    {
      for(int count = 0;count < size_;++count){
        delete reinterpret_cast<Bplustreeleaf<DATAPTR,DATAKEY>*>(ptr_[count]);
      }
    } else {
      for(int count = 0;count < size_;++count){
        delete reinterpret_cast<Bplustreenode<DATAPTR,DATAKEY>*>(ptr_[count]);
      }
    }
  };
  int     level_;
  int     size_;
  DATAKEY key_[_C::DEFAULT_BPLUSTREE_SIZE+1];
  void*   ptr_[_C::DEFAULT_BPLUSTREE_SIZE+1];
};

template <typename DATAPTR,typename DATAKEY>
class Bplustree : base::noncopyable{
using compare_func = std::function<bool(DATAKEY,DATAKEY,bool)>;
 public:
  using Bplustreeleaf_ = Bplustreeleaf<DATAPTR,DATAKEY>;
  using Bplustreenode_ = Bplustreenode<DATAPTR,DATAKEY>;
  Bplustree(compare_func func);
  ~Bplustree() = default;
  void* Insertdata(DATAPTR dataptr,DATAKEY key,void* beginptr);
  void Del_loop(); //before key include ==
  std::tuple<Bplustreeleaf<DATAPTR,DATAKEY>*,int> Find_leaf(DATAKEY key) ; //get before key last one index
  DATAKEY Get_cache_min_key() const;
  DATAPTR Get_cache_min_ptr() const;
  Bplustreeleaf<DATAPTR,DATAKEY>* Get_cache_min_leaf();
  bool Is_empty_and_cache();
  Bplustreeleaf<DATAPTR,DATAKEY>* Get_min_leaf();

  void* root_;
  int   treelevel_; //tree high, leaf node level
 private:
  // (2,1,true) return true
  // (2,2,true) return true
  // (2,2,false) return false
  compare_func                     compare_func_;
  void*                            min_leaf_cache_;
  std::deque<std::pair<void*,int>> Find_cache;
};

} // namespace net_tools::base::detail

namespace net_tools::base::detail{

template <typename DATAPTR,typename DATAKEY>
Bplustree<DATAPTR,DATAKEY>::Bplustree(compare_func func)
  :root_(new Bplustreenode<DATAPTR,DATAKEY>(1)),
   treelevel_(1),
   compare_func_(std::move(func)),
   Find_cache()
{
};

template <typename DATAPTR,typename DATAKEY>
void* Bplustree<DATAPTR,DATAKEY>::Insertdata(DATAPTR dataptr,DATAKEY key,void* beginptr){
  if(*reinterpret_cast<int*>(beginptr) == 0){ //leaf find
    Bplustreeleaf_* beginptr_ = reinterpret_cast<Bplustreeleaf_*>(beginptr);
    int begin_ = 0;
    int end_ = beginptr_->size_ - 1;
    if(end_ == -1) [[unlikely]] { //don't have data
      beginptr_->key_[0] = key;
      beginptr_->ptr_[0] = dataptr;
      beginptr_->size_++;
      return nullptr;
    }
    if( compare_func_(beginptr_->key_[end_],key,false)
        && compare_func_(key,beginptr_->key_[begin_],true) ) //begin <= key < end_ or size != 1
    {
      int index = 0;
      while(true){
        index = (begin_ + end_) >> 1;
        if(compare_func_(key,beginptr_->key_[index],true)) //key >= index
        {
          begin_ = index;
          if(compare_func_(beginptr_->key_[index+1],key,false)){ //key < index+1
            ++index;
            memmove(&beginptr_->key_[index+1],
                    &beginptr_->key_[index],
                    sizeof(DATAKEY)*(beginptr_->size_ - index));
            memmove(&beginptr_->ptr_[index+1],
                    &beginptr_->ptr_[index],
                    sizeof(DATAPTR)*(beginptr_->size_ - index));
            beginptr_->ptr_[index] = dataptr;
            beginptr_->key_[index] = key;
            beginptr_->size_++;
            break;
          }
        } else { //key < index
          end_ = index;
          if(compare_func_(key,beginptr_->key_[index-1],true)){ //key >= index-1
            memmove(&beginptr_->key_[index+1],
                    &beginptr_->key_[index],
                    sizeof(DATAKEY)*(beginptr_->size_ - index));
            memmove(&beginptr_->ptr_[index+1],
                    &beginptr_->ptr_[index],
                    sizeof(DATAPTR)*(beginptr_->size_ - index));
            beginptr_->ptr_[index] = dataptr;
            beginptr_->key_[index] = key;
            beginptr_->size_++;
            break;
          }
        }
      }
    } else { //begin > key or end <= key or size = 1
      if(compare_func_(key,beginptr_->key_[end_],true)) //key >= end or size = 1
      {
        ++end_;
        beginptr_->ptr_[end_] = dataptr;
        beginptr_->key_[end_] = key;
        beginptr_->size_++;
      } else { //key < begin
        memmove(&beginptr_->key_[begin_+1],
                &beginptr_->key_[begin_],
                sizeof(DATAKEY)*(beginptr_->size_));
        memmove(&beginptr_->ptr_[begin_+1],
                &beginptr_->ptr_[begin_],
                sizeof(DATAPTR)*(beginptr_->size_));
        beginptr_->ptr_[begin_] = dataptr;
        beginptr_->key_[begin_] = key;
        beginptr_->size_++;
      }
    }
    if(beginptr_->size_ > _C::DEFAULT_BPLUSTREE_SIZE){ // if full return new
      int mid = beginptr_->size_ >> 1;
      Bplustreeleaf_* ret = new Bplustreeleaf_();
      if(beginptr_->next_){
        beginptr_->next_->before_ = ret;
      }
      ret->next_ = beginptr_->next_;
      beginptr_->next_ = ret;
      ret->before_ = beginptr_;
      memcpy(&ret->key_[0],
             &beginptr_->key_[mid],
             sizeof(DATAKEY)*(beginptr_->size_ - mid));
      memcpy(&ret->ptr_[0],
             &beginptr_->ptr_[mid],
             sizeof(DATAPTR)*(beginptr_->size_ - mid));
      beginptr_->size_ = mid;
      ret->size_ = beginptr_->size_ - mid;
      return ret;
    } else {
      return nullptr;
    }
  } else {
    Bplustreenode_* beginptr_ = reinterpret_cast<Bplustreenode_*>(beginptr);
    int begin_ = 0;
    int end_ = beginptr_->size_ - 1;
    if(end_ == -1) [[unlikely]] { //don't have data
      if(beginptr_->level_ == 1){
        Bplustreeleaf_* new_ = new Bplustreeleaf_();
        Insertdata(dataptr,key,new_);
        beginptr_->key_[0] = new_->key_[0];
        beginptr_->ptr_[0] = new_;
        beginptr_->size_++;
        return nullptr;
      } else {
        Bplustreenode_* new_ = new Bplustreenode_(beginptr_->level_ - 1);
        Insertdata(dataptr,key,new_);
        beginptr_->key_[0] = new_->key_[0];
        beginptr_->ptr_[0] = new_;
        beginptr_->size_++;
        return nullptr;
      }
    }
    void* new_leaf = nullptr;
    if( compare_func_(beginptr_->key_[end_],key,false)
        && compare_func_(key,beginptr_->key_[begin_],true) ) //begin <= key < end_ size != 1
    {
      int index = 0;
      while(true){
        index = ((begin_ + end_) >> 1); // 0 + 1 >>1  ->0
        if(compare_func_(key,beginptr_->key_[index],true)) //key >= index
        {
          begin_ = index;
          if(compare_func_(beginptr_->key_[index+1],key,false)){ //key < index+1
            if((new_leaf = Insertdata(dataptr,key,beginptr_->ptr_[index]))){
              ++index;
              memmove(&beginptr_->key_[index+1],
                      &beginptr_->key_[index],
                      sizeof(DATAKEY)*(beginptr_->size_ - index));
              memmove(&beginptr_->ptr_[index+1],
                      &beginptr_->ptr_[index],
                      sizeof(void*)*(beginptr_->size_ - index));
              beginptr_->key_[index] = reinterpret_cast<Bplustreeleaf_*>(new_leaf)->key_[0];
              beginptr_->ptr_[index] = new_leaf;
              ++beginptr_->size_;
            }
            break;
          }
        } else { //key < index
          end_ = index;
          if(compare_func_(key,beginptr_->key_[index-1],true)){ //key >= index-1
            if((new_leaf = Insertdata(dataptr,key,beginptr_->ptr_[index-1]))){
              memmove(&beginptr_->key_[index+1],
                      &beginptr_->key_[index],
                      sizeof(DATAKEY)*(beginptr_->size_ - index));
              memmove(&beginptr_->ptr_[index+1],
                      &beginptr_->ptr_[index],
                      sizeof(void*)*(beginptr_->size_ - index));
              beginptr_->key_[index] = reinterpret_cast<Bplustreeleaf_*>(new_leaf)->key_[0];
              beginptr_->ptr_[index] = new_leaf;
              beginptr_->size_++;
            }
            break;
          }
        }
      }
    } else { //begin > key or end <= key or size = 1
      if(compare_func_(key,beginptr_->key_[end_],true)) //key >= end or size = 1
      {
        if((new_leaf = Insertdata(dataptr,key,beginptr_->ptr_[end_]))){
          beginptr_->key_[end_+1] = reinterpret_cast<Bplustreeleaf_*>(new_leaf)->key_[0];
          beginptr_->ptr_[end_+1] = new_leaf;
          beginptr_->size_++;
        }
      } else { //key < begin
        if((new_leaf = Insertdata(dataptr,key,beginptr_->ptr_[begin_]))){
          ++begin_;
          memmove(&beginptr_->key_[begin_+1],
                  &beginptr_->key_[begin_],
                  sizeof(DATAKEY)*(beginptr_->size_));
          memmove(&beginptr_->ptr_[begin_+1],
                  &beginptr_->ptr_[begin_],
                  sizeof(void*)*(beginptr_->size_));
          beginptr_->key_[begin_+1] = reinterpret_cast<Bplustreeleaf_*>(new_leaf)->key_[0];
          beginptr_->ptr_[begin_+1] = new_leaf;
          beginptr_->size_++;
        }
        beginptr_->key_[0] = reinterpret_cast<Bplustreeleaf_*>(beginptr_->ptr_[0])->key_[0];
      }
    }
    if(beginptr_->size_ > _C::DEFAULT_BPLUSTREE_SIZE){ // if full return new
      int mid = beginptr_->size_ >> 1;
      Bplustreenode_* ret = new Bplustreenode_(beginptr_->level_);
      memcpy(&ret->key_[0],
             &beginptr_->key_[mid],
             sizeof(DATAKEY)*(beginptr_->size_ - mid));
      memcpy(&ret->ptr_[0],
             &beginptr_->ptr_[mid],
             sizeof(void*)*(beginptr_->size_ - mid));
      beginptr_->size_ = mid;
      ret->size_ = beginptr_->size_ - mid;
      if(beginptr_->level_ == treelevel_){ //最顶层
        Bplustreenode_* root = new Bplustreenode_(beginptr_->level_ + 1);
        root->key_[0] = beginptr_->key_[0];
        root->ptr_[0] = beginptr_;
        root->key_[1] = ret->key_[0];
        root->ptr_[1] = ret;
        root_ = root;
        ++treelevel_;
        return nullptr;
      }
      return ret;
    } else {
      return nullptr;
    }
  }
};

template <typename DATAPTR,typename DATAKEY>
void Bplustree<DATAPTR,DATAKEY>::Del_loop(){
  int index = 0;
  bool del = false;
  long unsigned int begin_size = 0;
  begin_size = Find_cache.size();
  bool nothing = false;
  while (!Find_cache.empty())
  {
    index = Find_cache.crbegin()->second;
    if(index == -1 || nothing){
      nothing = true;
      Find_cache.pop_back();
    }
    if(Find_cache.size() == begin_size){ //leaf ptr
      Bplustreeleaf_* begin = reinterpret_cast<Bplustreeleaf_*>(Find_cache.crbegin()->first);
      begin->before_ = nullptr;
      for(int count = 0;count <= index;count++){
        delete reinterpret_cast<DATAPTR>(begin->ptr_[count]);
      }
      memcpy(&begin->key_[0],
             &begin->key_[index + 1],
             sizeof(DATAKEY)*(begin->size_ - index - 1));
      memcpy(&begin->ptr_[0],
             &begin->ptr_[index + 1],
             sizeof(DATAPTR)*(begin->size_ - index - 1));
      begin->size_ = begin->size_ - index - 1;
      if(begin->size_ == 0){
        del = true;
      }
    } else {
      index = Find_cache.crbegin()->second;
      Bplustreenode_* begin = reinterpret_cast<Bplustreenode_*>(Find_cache.crbegin()->first);
      for(int count = 0;count < index;++count){
        if(begin->ptr_[count]){
          delete reinterpret_cast<Bplustreenode_*>(begin->ptr_[count]);
        }
      }
      if (del) //下一层一个节点被删除
      {
        del = false;
        if(begin->level_ == 1){
          delete reinterpret_cast<Bplustreeleaf_*>(begin->ptr_[index]);
        } else {
          delete reinterpret_cast<Bplustreenode_*>(begin->ptr_[index]);
        }
        ++index;
        if(index == begin->size_){ //该层因为下层删除而清空
          if(Find_cache.size() == 1){ //最顶层 空树
            begin->size_ = 0;
            begin->level_ = 1;
            treelevel_ = 1;
            root_ = begin;
          }
          del = true;
        }
      }
      if(!del){ //该层没被清空
        memcpy(&begin->key_[0],
               &begin->key_[index],
               sizeof(DATAKEY)*(begin->size_ - index));
        memcpy(&begin->ptr_[0],
               &begin->ptr_[index],
               sizeof(void*)*(begin->size_ - index));
        begin->key_[0] = reinterpret_cast<Bplustreenode_*>(begin->ptr_[0])->key_[0];
        begin->size_ = begin->size_ - index;
        if(begin->size_ == 1 && Find_cache.size() == 1 && begin->level_ != 1){ //该层只剩一个节点且为最顶层且不为level1 则减小树的大小
          root_ = begin->ptr_[0];
          treelevel_ =  reinterpret_cast<Bplustreenode_*>(root_)->level_;
          begin->size_ = 0; //避免该树清空
          delete begin; //回收root
        }
      }
    }
    Find_cache.pop_back();
  }
};
//must than call del_loop
template <typename DATAPTR,typename DATAKEY>
std::tuple<Bplustreeleaf<DATAPTR,DATAKEY>*,int> Bplustree<DATAPTR,DATAKEY>::Find_leaf(DATAKEY key){
  void* beginptr_ =  root_;
  // Find_cache should be empty ,can debug here
  for(;;){
    if(*reinterpret_cast<int*>(beginptr_) == 0){ //leaf
      Bplustreeleaf_* beginptr = reinterpret_cast<Bplustreeleaf_*>(beginptr_);
      int begin_ = 0;
      int end_ = beginptr->size_ - 1;
      if(end_ == -1) [[unlikely]] {
        exit(2);
      } //can't be -1, because must have data and timeout to call Find_leaf // debug
      int index = 0;
      if(compare_func_(beginptr->key_[end_],key,false)){ //key < end_
        while (true)
        {
          index = (begin_ + end_) >> 1;
          if(compare_func_(key,beginptr->key_[index],true)){ //key >= index
            begin_ = index;
            if(compare_func_(beginptr->key_[index+1],key,false)){ //key < index+1
              break;
            }
          } else { //key < index
            end_ = index;
            if(compare_func_(key,beginptr->key_[index-1],true)){ //key >= index-1
              --index;
              break;
            }
          }
        }
      } else { // end <= key or size = 1
        if(end_ == 0){
          if(compare_func_(key,beginptr->key_[end_],true)){ // key >= end
            index = end_;
          }else{
            index = -1;
          }
        }else{
          index = end_;
        }
      }
      Find_cache.push_back(std::make_pair(beginptr,index));
      return std::make_tuple(beginptr,index);
    } else {
      Bplustreenode_* beginptr = reinterpret_cast<Bplustreenode_*>(beginptr_);
      int begin_ = 0;
      int end_ = beginptr->size_ - 1;
      int index = 0;
      if(compare_func_(beginptr->key_[end_],key,false)){ //key < end_
        while (true)
        {
          index = (begin_ + end_) >> 1;
          if(compare_func_(key,beginptr->key_[index],true)){ //key >= index
            begin_ = index;
            if(compare_func_(beginptr->key_[index+1],key,false)){ //key < index+1
              break;
            }
          } else { //key < index
            end_ = index;
            if(compare_func_(key,beginptr->key_[index-1],true)){ //key >= index-1
              --index;
              break;
            }
          }
        }
      } else { //end <= key or size = 1
        if(end_ == 0){
          if(compare_func_(key,beginptr->key_[end_],true)){ // key >= end
            index = end_;
          }else{
            index = -1;
          }
        }else{
          index = end_;
        }
      }
      if(index == -1){
        for(int level = *reinterpret_cast<int*>(beginptr_);level >0;--level){
          Find_cache.push_back(std::make_pair(beginptr,0));
          beginptr_ = reinterpret_cast<void*>(beginptr->ptr_[0]);
        }
        Find_cache.push_back(std::make_pair(beginptr,-1));
        Bplustreeleaf_* beginptr = reinterpret_cast<Bplustreeleaf_*>(beginptr_);
        return std::make_tuple(beginptr,-1);
      }else{
        Find_cache.push_back(std::make_pair(beginptr,index));
        beginptr_ = reinterpret_cast<void*>(beginptr->ptr_[index]);
      }
    }
  }
};

template <typename DATAPTR,typename DATAKEY>
DATAKEY Bplustree<DATAPTR,DATAKEY>::Get_cache_min_key() const {
  return reinterpret_cast<Bplustreeleaf_*>(min_leaf_cache_)->key_[0];
};

template <typename DATAPTR,typename DATAKEY>
DATAPTR Bplustree<DATAPTR,DATAKEY>::Get_cache_min_ptr() const {
  return reinterpret_cast<Bplustreeleaf_*>(min_leaf_cache_)->ptr_[0];
};

template <typename DATAPTR,typename DATAKEY>
Bplustreeleaf<DATAPTR,DATAKEY>* Bplustree<DATAPTR,DATAKEY>::Get_min_leaf(){
  Bplustreenode_* begin = reinterpret_cast<Bplustreenode_*>(root_);
  for(;;){
    if(*reinterpret_cast<int*>(begin) == 0){
      Bplustreeleaf_* end = reinterpret_cast<Bplustreeleaf_*>(begin);
      if(end->size_ == 0) [[unlikely]] {
        return nullptr;
      } else {
        return end;
      }
    }
    if(begin->size_){
      begin = reinterpret_cast<Bplustreenode_*>(begin->ptr_[0]);
    }else{
      return nullptr;
    }
  }
};

template <typename DATAPTR,typename DATAKEY>
bool Bplustree<DATAPTR,DATAKEY>::Is_empty_and_cache(){
  Bplustreenode_* ret = reinterpret_cast<Bplustreenode_*>(Get_min_leaf());
  if(ret){
    min_leaf_cache_ = ret;
    return false;
  }else{
    min_leaf_cache_ = nullptr;
    return true;
  }
};

} // namespace net_tools::base::detail